package leetcode.editor.offer;

// 剑指 Offer 56 - I. 数组中数字出现的次数
// https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
class ShuZuZhongShuZiChuXianDeCiShuLcof {
    public static void main(String[] args) {
        Solution solution = new ShuZuZhongShuZiChuXianDeCiShuLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    // https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
    class Solution {
        public int[] singleNumbers(int[] nums) {
            // 使用异或：相同为0，和0异或为非0那个数
            // 最终n为两个只出现一次的数的异或结果
            int x = 0, y = 0, n = 0, m = 1;
            for (int num : nums) {
                n ^= num;
            }

            // 找出最后一位不为0
            while ((n & m) == 0) {
                m <<= 1;
            }

            // 对最后一位不为0进行分组异或，最终剩下的就是两个只出现一次的数字
            for (int num : nums) {
                if ((num & m) != 0) x ^= num;
                else y ^= num;
            }

            return new int[]{x, y};
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
